/**
 * This class represents the Games underlying main data structure, aka the SpaceTree.
 * 
 * @author (Dilyan GEORGIEV)
 * @author (Thomas KOBER)
 * @author (Matthew MCDONALD)
 * 
 * @version (1.0)
 */
public class SpaceTree<E> implements Cloneable
{
    ////////////////////////////////////////////////////////////////////////////////
    // Field declarations
    ////////////////////////////////////////////////////////////////////////////////
    
    // The Trees root node
    private SpaceNode root;
    // The Trees size
    private int size;
    
    ////////////////////////////////////////////////////////////////////////////////
    // Constructor(s)
    ////////////////////////////////////////////////////////////////////////////////
    
    /**
     * Constructor for objects of class SpaceTree
     * @param root the Trees Root data.
     */
    public SpaceTree(E root)
    {
        this.root = new SpaceNode<E>(null, root);
        this.size = 1;
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    // Public Implementation
    ////////////////////////////////////////////////////////////////////////////////
    
    /**
     * Returns the Trees root.
     * @return the Trees root.
     */
    public SpaceNode<E> getRoot()
    {
        return this.root;
    }
    
    /**
     * Returns the parent of the given node.
     * @param n the node to get the parent for.
     * @return the parent of the given node.
     */
    public SpaceNode<E> getParent(SpaceNode<E> n)
    {
        return n.getParent();
    }
    
    /**
     * Inserts and returns a left child for the given node.
     * @param n the parent for which to insert a left child.
     * @param data the data of the left child.
     * @return the newly inserted left child node.
     */
    public SpaceNode<E> insertLeft(SpaceNode<E> n, E data) 
    {
        if (n.getLeft() != null) {
            // TODO: Throw Exception
        }
        
        SpaceNode<E> newLeft = new SpaceNode<E>(n, data);
        
        n.setLeft(newLeft);
        size++;
        
        return newLeft;
    }
    
    /**
     * Inserts and returns a right child for the given node.
     * @param n the parent for which to insert a right child.
     * @param data the data of the right child.
     * @return the newly inserted right child node.
     */
    public SpaceNode<E> insertRight(SpaceNode<E> n, E data) 
    {
        if (n.getRight() != null) {
            // TODO: throw Excepiton
        }
        
        SpaceNode<E> newRight = new SpaceNode<E>(n, data);
        
        n.setRight(newRight);
        size++;
        
        return newRight;
    }
    
    /**
     * Returns the given nodes right child.
     * @param the node to get the right child of.
     * @return the given nodes right child.
     */
    public SpaceNode<E> getRight(SpaceNode<E> n)
    {
        if (n.getRight() == null) {
            // TODO: throw Exception
        }
        
        return n.getRight();
    }
    
    /**
     * Returns whether or not the given node has a right child.
     * @param the node for which to check for a right child.
     * @return true if the given node has a right child, false otherwise.
     */
    public boolean hasRight(SpaceNode<E> n)
    {
        return n.getRight() != null;
    }
    
    /**
     * Returns the given nodes left child.
     * @param the node to get the left child of.
     * @return the given nodes left child.
     */
    public SpaceNode<E> getLeft(SpaceNode<E> n)
    {
        if (n.getLeft() == null) {
            // TODO: Throw Exception
        }
        
        return n.getLeft();
    }
    
    /**
     * Returns whether or not the given node has a left child.
     * @param the node for which to check for a left child.
     * @return true if the given node has a left child, false otherwise.
     */
    public boolean hasLeft(SpaceNode<E> n)
    {
        return n.getLeft() != null;
    }
    
    /**
     * Returns whether or not the given node is the root node.
     * @param n the node for which to check if its the root node.
     * @return true if the given node is the root node, false otherwise.
     */
    public boolean isRoot(SpaceNode<E> n)
    {
        return this.root.equals(n);
    }
    
    /**
     * Returns whether or not the given node is a leaf (terminal) node.
     * @param n the node for which to check if it is a leaf.
     * @return true if the given node is a leaf, false otherwise.
     */
    public boolean isLeaf(SpaceNode<E> n)
    {
        return n.getLeft() == null && n.getRight() == null;
    }
    
    /**
     * Returns the size of the tree.
     * @return the size of the tree.
     */
    public int size()
    {
        return this.size;
    }
    
    /**
     * Returns whether or not the tree is empty.
     * @return true if the tree is empty, false otherwise.
     */
    public boolean isEmpty()
    {
        return this.size <= 0;
    }
    
    // Cloneable Implementation
    public SpaceTree<E> clone()
    {
        SpaceTree theCopy = null;
        
        try {
            theCopy = (SpaceTree)super.clone();
            theCopy.root = this.root.clone();
            theCopy = this.deepClone(theCopy, this.root);
        } catch (CloneNotSupportedException ex) {
            // Cant happen
            ex.printStackTrace();
        }
        
        return theCopy;
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    // Private Implementation
    ////////////////////////////////////////////////////////////////////////////////
    
    /**
     * Creates a deep clone of the current tree.
     * @param clonedTree the freshly cloned object template.
     * @param originalNode the node to be cloned and inserted into the cloned tree.
     * @return the finished clone.
     */
    private SpaceTree<E> deepClone(SpaceTree<E> clonedTree, SpaceNode<E> originalNode)
    {
        
        if (this.hasLeft(originalNode)) {
            clonedTree.insertLeft(originalNode, originalNode.getLeft().getData());
            return this.deepClone(clonedTree, originalNode.getLeft());
        } else if (this.hasRight(originalNode)) {
            clonedTree.insertRight(originalNode, originalNode.getRight().getData());
            return this.deepClone(clonedTree, originalNode.getRight());
        }
        
        return clonedTree;
    }
}
